package com.sourcetrip.raw.adt;


import com.sourcetrip.raw.adt.abs.MyAbstractLinkedList;

/**
 * @author: ZhouBert
 * @date: 2020/11/18
 * @description: 双向链表
 * 承接知识点：
 * 查询效率可能高于单向链表：当查找靠近尾部的节点时；
 * ---
 * 在我的设计里，确实为双向循环链表，但是多了指向尾节点的指针 last 用于辅助判断。
 * ---
 * 搞链表还是对着图比较清晰
 */
public class MyDoublyLinkedList<E> extends MyAbstractLinkedList<E> {

	/**
	 * 哨兵节点
	 * 如果只有一个哨兵节点，使用 pre 时很麻烦，因为 尾节点 又需要遍历一遍！
	 */
	private MyDoublyNode<E> guard = new MyDoublyNode<>(null, null, null);
	/**
	 * 指向尾节点
	 * 但是当我添加了 尾节点的时候
	 * --
	 * 原先通过 尾节点进行辅助判断，但是后来发现尾节点可以不存在，只要保证能让 guard 指向尾节点即可
	 */
	private MyDoublyNode<E> last = new MyDoublyNode<>(null, null, null);


	@Override
	public E get(int index) {
		checkIndex4get(index);
		return node(index).getElement();
	}

	@Override
	public void add(int index, E element) {
		checkIndex4add(index);
		// pre 是绝对安全的，因为有哨兵节点
		MyDoublyNode<E> pre = node(index - 1);
		MyDoublyNode<E> cur = pre.getNext();
		pre.setNext(new MyDoublyNode<>(pre, cur, element));
		// 而后一个节点，是可能产生 NullPointException 的：当为空时
		if (cur != null) {
			cur.setPre(pre.getNext());
		}

		size++;
		//如果添加的是最后一个元素，那么让尾节点指向刚刚添加的元素
		if (size == index + 1) {
//			last = pre.getNext();
//			//让哨兵节点的 pre 指向 last
//			guard.setPre(last);

			guard.setPre(pre.getNext());
		}


	}


	@Override
	public E set(int index, E element) {
		checkIndex4get(index);
		MyDoublyNode<E> cur = node(index);
		E oldValue = cur.getElement();
		cur.setElement(element);
		return oldValue;
	}

	@Override
	public E remove(int index) {
		checkIndex4get(index);
		// 拿到需要移除的 node
		MyDoublyNode<E> cur = node(index);
		MyDoublyNode<E> pre = cur.getPre();
		MyDoublyNode<E> next = cur.getNext();
		pre.setNext(next);
		if (next!=null){
			next.setPre(pre);
		}

		cur.setPre(null);
		cur.setNext(null);
		size--;
		//如果删除的是末尾的元素
		if (size==index){
			guard.setPre(pre);
		}
		return cur.getElement();
	}

	/**
	 * 毕竟还是要遍历，就顺序好了
	 *
	 * @param element
	 * @return
	 */
	@Override
	public int indexOf(E element) {
		MyDoublyNode<E> node = this.guard;
		if (element == null) {
			for (int i = 0; i < size; i++) {
				node = node.getNext();
				if (node.getElement() == null) {
					return i;
				}
			}
		} else {
			for (int i = 0; i < size; i++) {
				node = node.getNext();
				if (element.equals(node.getElement())) {
					return i;
				}
			}
		}
		return -1;
	}

	@Override
	public void clear() {
		guard.setNext(null);
		guard.setPre(null);
		size = 0;
	}

	@Override
	public String toString() {
		MyDoublyNode<E> node = this.guard.getNext();
		StringBuilder sb = new StringBuilder();
		sb.append("[");

		//region	version 1

//		while (node != last) {
//			sb.append(node.getElement());
//			node = node.getNext();
//			sb.append(", ");
//		}
//		//最后剩下一个 last
//		sb.append(node.getElement());
//		sb.append("]");

		//endregion

		//region	version2

		while (node != null) {
			sb.append(node.getElement());
			node = node.getNext();
			if (node != null) {
				sb.append(", ");
			}
		}
		sb.append("]");
		//endregion


		return sb.toString();
	}

	//region	private methods

	/**
	 * 获取“索引”下的节点
	 * 由于使用了双向链表，那么就判断一下 index 靠近 0 还是 size
	 * -> 拿 index 与 size 的一半进行比较
	 *
	 * @param index
	 * @return
	 */
	private MyDoublyNode<E> node(int index) {
		MyDoublyNode<E> node = guard;
		//除以2
		int num = size >> 1;
		//移动步数
		int step = 0;
		//如果 index 大于 num,从尾节点进行倒数
		if (index > num) {
			step = size - index;
			for (int i = 0; i < step; i++) {
				node = node.getPre();
			}
			return node;
		} else {
			step = index + 1;
			for (int i = 0; i < step; i++) {
				node = node.getNext();
			}
			return node;
		}
	}


	//endregion
}
